package week_03;

/**
 * 200. 岛屿数量
 * 给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 * 示例 1：
 * <p>
 * 输入：grid = [
 * ["1","1","1","1","0"],
 * ["1","1","0","1","0"],
 * ["1","1","0","0","0"],
 * ["0","0","0","0","0"]
 * ]
 * 输出：1
 * <p>
 * 示例 2：
 * <p>
 * 输入：grid = [
 * ["1","1","0","0","0"],
 * ["1","1","0","0","0"],
 * ["0","0","1","0","0"],
 * ["0","0","0","1","1"]
 * ]
 * 输出：3
 */
public class NumIslands_DFS_200 {
    public int[] dx = new int[]{-1, 0, 0, 1};
    public int[] dy = new int[]{0, -1, 1, 0};
    private int n;
    private int m;
    private boolean[][] visited;
    private int ans;

    public int numIslands(char[][] grid) {
        n = grid.length;
        m = grid[0].length;
        visited = new boolean[n][m];
        ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 没有访问过的新1 才进入新一轮搜索
                if(grid[i][j]=='1'&&!visited[i][j]){
                    System.out.println(visited[i][j]);
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    private void dfs(char[][] grid, int x, int y) {
        visited[x][y] = true;
        // 合法的点才会进来搜上下左右
        for (int i = 0; i < 4; i++) {
            // 搜下一个点是否要下扩
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (grid[nx][ny] == '1' && !visited[nx][ny]) {
                dfs(grid, nx, ny);
            }
        }
    }

}
